package com.yanceysong.codetop.s91_s100;

import com.yanceysong.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class S93_Easy_226_翻转二叉树 {
    /**
     * .S93_Easy_226_翻转二叉树
     * .<p>
     * .<a href="https://leetcode.cn/problems/invert-binary-tree/">...</a>
     * .<p>
     * .给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     * .<p>
     * .示例：
     * .<p>
     * .输入：root = [4,2,7,1,3,6,9]
     * .输出：[4,7,2,9,6,3,1]
     * .<p>
     * .输入：root = [2,1,3]
     * .输出：[2,3,1]
     * .<p>
     * .输入：root = []
     * .输出：[]
     * .<p>
     * .提示：
     * .<p>
     * .树中节点数目范围在 [0, 100] 内
     * .-100 <= Node.val <= 100
     * .<p>
     * .核心标签：树、深度优先搜索、广度优先搜索、二叉树、递归
     * .<p>
     * .算法原理：递归翻转二叉树
     * .- 翻转一棵二叉树，就是将每个节点的左右子树交换
     * .- 使用递归的方式，先递归翻转左右子树，然后交换当前节点的左右子树
     * .- 递归的终止条件是节点为空
     * .<p>
     * .关键洞察：
     * .1. 翻转二叉树本质上是一个递归问题
     * .2. 对于每个节点，只需要交换它的左右子节点
     * .3. 然后递归地翻转左右子树
     * .4. 这是一个后序遍历的变体（先处理子树，再处理当前节点）
     * .<p>
     * .图解示例：
     * .<p>
     * .原始二叉树：
     * .4
     * ./   \
     * .2     7
     * ./ \   / \
     * .1   3 6   9
     * .<p>
     * .翻转后的二叉树：
     * .4
     * ./   \
     * .7     2
     * ./ \   / \
     * .9   6 3   1
     * .<p>
     * .递归过程详解（以上面的树为例）：
     * .<p>
     * .步骤1：从根节点4开始
     * .4
     * ./   \
     * .2     7
     * ./ \   / \
     * .1   3 6   9
     * .<p>
     * .步骤2：递归翻转左子树（节点2）
     * .2
     * ./ \
     * .1   3
     * .↓ 翻转后
     * .2
     * ./ \
     * .3   1
     * .<p>
     * .步骤3：递归翻转右子树（节点7）
     * .7
     * ./ \
     * .6   9
     * .↓ 翻转后
     * .7
     * ./ \
     * .9   6
     * .<p>
     * .步骤4：交换节点4的左右子树
     * .4              4
     * ./   \    →    /   \
     * .2     7        7     2
     * ./ \   / \      / \   / \
     * .3   1 9   6    9   6 3   1
     * .<p>
     * .递归调用栈示例（简化版）：
     * .invertTree(4)
     * .├─ invertTree(2)
     * .│  ├─ invertTree(1) → return 1
     * .│  ├─ invertTree(3) → return 3
     * .│  └─ swap(2.left, 2.right) → return 2
     * .├─ invertTree(7)
     * .│  ├─ invertTree(6) → return 6
     * .│  ├─ invertTree(9) → return 9
     * .│  └─ swap(7.left, 7.right) → return 7
     * .└─ swap(4.left, 4.right) → return 4
     * .<p>
     * .时间复杂度：O(n)，其中n为二叉树节点数量
     * .- 需要访问每个节点恰好一次
     * .<p>
     * .空间复杂度：O(h)，其中h为二叉树的高度
     * .- 递归调用栈的深度取决于树的高度
     * .- 最坏情况（链式树）：O(n)
     * .- 最好情况（完全平衡树）：O(log n)
     */
    public TreeNode invertTree(TreeNode root) {
        // 递归终止条件：如果节点为空，直接返回null
        if (root == null) {
            return null;
        }

        // 递归翻转左子树，得到翻转后的左子树根节点
        TreeNode leftSubtree = invertTree(root.left);
        // 递归翻转右子树，得到翻转后的右子树根节点
        TreeNode rightSubtree = invertTree(root.right);

        // 交换当前节点的左右子树
        root.left = rightSubtree;
        root.right = leftSubtree;

        // 返回当前节点（已完成翻转）
        return root;
    }

    /**
     * .方法二：迭代法（使用队列进行层序遍历）
     * .<p>
     * .使用广度优先搜索（BFS）的方式翻转二叉树
     * .- 使用队列存储待处理的节点
     * .- 对于每个节点，交换其左右子节点
     * .- 然后将左右子节点加入队列继续处理
     * .<p>
     * .时间复杂度：O(n)
     * .空间复杂度：O(n)，队列中最多存储一层的节点
     */
    public TreeNode invertTreeIterative(TreeNode root) {
        // 边界条件检查
        if (root == null) {
            return null;
        }

        // 创建队列用于层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 当队列不为空时，继续处理
        while (!queue.isEmpty()) {
            // 取出队首节点
            TreeNode currentNode = queue.poll();

            // 交换当前节点的左右子节点
            TreeNode temp = currentNode.left;
            currentNode.left = currentNode.right;
            currentNode.right = temp;

            // 将左子节点加入队列（如果存在）
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }

            // 将右子节点加入队列（如果存在）
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }

        return root;
    }

    public static void main(String[] args) {
        S93_Easy_226_翻转二叉树 solution = new S93_Easy_226_翻转二叉树();

        System.out.println("=== 翻转二叉树测试开始 ===");

        // 测试1: 完整二叉树 - 题目示例1 [4,2,7,1,3,6,9]
        System.out.println("\n--- 测试1: 完整二叉树 [4,2,7,1,3,6,9] ---");
        testCase1(solution);

        // 测试2: 简单二叉树 - 题目示例2 [2,1,3]
        System.out.println("\n--- 测试2: 简单二叉树 [2,1,3] ---");
        testCase2(solution);

        // 测试3: 空树 - 题目示例3 []
        System.out.println("\n--- 测试3: 空树 [] ---");
        testEmptyTree(solution);

        // 测试4: 单节点树
        System.out.println("\n--- 测试4: 单节点树 [1] ---");
        testSingleNode(solution);

        // 测试5: 只有左子树的树
        System.out.println("\n--- 测试5: 只有左子树 [1,2,null,3] ---");
        testLeftSkewedTree(solution);

        // 测试6: 只有右子树的树
        System.out.println("\n--- 测试6: 只有右子树 [1,null,2,null,3] ---");
        testRightSkewedTree(solution);

        // 测试7: 完全二叉树
        System.out.println("\n--- 测试7: 完全二叉树 [1,2,3,4,5,6] ---");
        testCompleteBinaryTree(solution);

        // 测试8: 迭代法测试
        System.out.println("\n--- 测试8: 迭代法翻转 [4,2,7,1,3,6,9] ---");
        testIterativeMethod(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试完整二叉树 - [4,2,7,1,3,6,9]
     * .原始树：
     * .4
     * ./   \
     * .2     7
     * ./ \   / \
     * .1   3 6   9
     * .<p>
     * .翻转后：
     * .4
     * ./   \
     * .7     2
     * ./ \   / \
     * .9   6 3   1
     */
    private static void testCase1(S93_Easy_226_翻转二叉树 solution) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        System.out.println("原始树结构:");
        System.out.println("       4");
        System.out.println("      / \\");
        System.out.println("     2   7");
        System.out.println("    / \\ / \\");
        System.out.println("   1  3 6  9");

        TreeNode result = solution.invertTree(root);

        System.out.println("\n翻转后树结构:");
        System.out.println("       4");
        System.out.println("      / \\");
        System.out.println("     7   2");
        System.out.println("    / \\ / \\");
        System.out.println("   9  6 3  1");

        // 验证结果
        assert result.val == 4 : "根节点应该是4";
        assert result.left.val == 7 : "根节点的左子节点应该是7";
        assert result.right.val == 2 : "根节点的右子节点应该是2";
        assert result.left.left.val == 9 : "节点7的左子节点应该是9";
        assert result.left.right.val == 6 : "节点7的右子节点应该是6";
        assert result.right.left.val == 3 : "节点2的左子节点应该是3";
        assert result.right.right.val == 1 : "节点2的右子节点应该是1";

        System.out.println("✓ 完整二叉树翻转测试通过");
    }

    /**
     * .测试简单二叉树 - [2,1,3]
     * .原始树：
     * .2
     * ./ \
     * .1   3
     * .<p>
     * .翻转后：
     * .2
     * ./ \
     * .3   1
     */
    private static void testCase2(S93_Easy_226_翻转二叉树 solution) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        System.out.println("原始树结构:");
        System.out.println("   2");
        System.out.println("  / \\");
        System.out.println(" 1   3");

        TreeNode result = solution.invertTree(root);

        System.out.println("\n翻转后树结构:");
        System.out.println("   2");
        System.out.println("  / \\");
        System.out.println(" 3   1");

        // 验证结果
        assert result.val == 2 : "根节点应该是2";
        assert result.left.val == 3 : "根节点的左子节点应该是3";
        assert result.right.val == 1 : "根节点的右子节点应该是1";

        System.out.println("✓ 简单二叉树翻转测试通过");
    }

    /**
     * .测试空树 - []
     */
    private static void testEmptyTree(S93_Easy_226_翻转二叉树 solution) {
        System.out.println("原始树结构: null");

        TreeNode result = solution.invertTree(null);

        System.out.println("翻转后树结构: null");

        // 验证结果
        assert result == null : "空树翻转后应该还是null";

        System.out.println("✓ 空树翻转测试通过");
    }

    /**
     * .测试单节点树 - [1]
     */
    private static void testSingleNode(S93_Easy_226_翻转二叉树 solution) {
        TreeNode root = new TreeNode(1);

        System.out.println("原始树结构: 1");

        TreeNode result = solution.invertTree(root);

        System.out.println("翻转后树结构: 1");

        // 验证结果
        assert result.val == 1 : "根节点应该是1";
        assert result.left == null : "左子节点应该为null";
        assert result.right == null : "右子节点应该为null";

        System.out.println("✓ 单节点树翻转测试通过");
    }

    /**
     * .测试只有左子树的树 - [1,2,null,3]
     * .原始树：
     * .1
     * ./
     * .2
     * ./
     * .3
     * .<p>
     * .翻转后：
     * .1
     * .\
     * .2
     * .\
     * .3
     */
    private static void testLeftSkewedTree(S93_Easy_226_翻转二叉树 solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);

        System.out.println("原始树结构:");
        System.out.println("   1");
        System.out.println("  /");
        System.out.println(" 2");
        System.out.println("/");
        System.out.println("3");

        TreeNode result = solution.invertTree(root);

        System.out.println("\n翻转后树结构:");
        System.out.println("1");
        System.out.println(" \\");
        System.out.println("  2");
        System.out.println("   \\");
        System.out.println("    3");

        // 验证结果
        assert result.val == 1 : "根节点应该是1";
        assert result.left == null : "根节点的左子节点应该为null";
        assert result.right.val == 2 : "根节点的右子节点应该是2";
        assert result.right.right.val == 3 : "节点2的右子节点应该是3";

        System.out.println("✓ 左偏树翻转测试通过");
    }

    /**
     * .测试只有右子树的树 - [1,null,2,null,3]
     * .原始树：
     * .1
     * .\
     * .2
     * .\
     * .3
     * .<p>
     * .翻转后：
     * .1
     * ./
     * .2
     * ./
     * .3
     */
    private static void testRightSkewedTree(S93_Easy_226_翻转二叉树 solution) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);

        System.out.println("原始树结构:");
        System.out.println("1");
        System.out.println(" \\");
        System.out.println("  2");
        System.out.println("   \\");
        System.out.println("    3");

        TreeNode result = solution.invertTree(root);

        System.out.println("\n翻转后树结构:");
        System.out.println("   1");
        System.out.println("  /");
        System.out.println(" 2");
        System.out.println("/");
        System.out.println("3");

        // 验证结果
        assert result.val == 1 : "根节点应该是1";
        assert result.right == null : "根节点的右子节点应该为null";
        assert result.left.val == 2 : "根节点的左子节点应该是2";
        assert result.left.left.val == 3 : "节点2的左子节点应该是3";

        System.out.println("✓ 右偏树翻转测试通过");
    }

    /**
     * .测试完全二叉树 - [1,2,3,4,5,6]
     * .原始树：
     * .1
     * ./   \
     * .2     3
     * ./ \   /
     * .4   5 6
     * .<p>
     * .翻转后：
     * .1
     * ./   \
     * .3     2
     * .\   / \
     * .6 5   4
     */
    private static void testCompleteBinaryTree(S93_Easy_226_翻转二叉树 solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        System.out.println("原始树结构:");
        System.out.println("     1");
        System.out.println("    / \\");
        System.out.println("   2   3");
        System.out.println("  / \\ /");
        System.out.println(" 4  5 6");

        TreeNode result = solution.invertTree(root);

        System.out.println("\n翻转后树结构:");
        System.out.println("     1");
        System.out.println("    / \\");
        System.out.println("   3   2");
        System.out.println("    \\ / \\");
        System.out.println("    6 5  4");

        // 验证结果
        assert result.val == 1 : "根节点应该是1";
        assert result.left.val == 3 : "根节点的左子节点应该是3";
        assert result.right.val == 2 : "根节点的右子节点应该是2";
        assert result.left.right.val == 6 : "节点3的右子节点应该是6";
        assert result.right.left.val == 5 : "节点2的左子节点应该是5";
        assert result.right.right.val == 4 : "节点2的右子节点应该是4";

        System.out.println("✓ 完全二叉树翻转测试通过");
    }

    /**
     * .测试迭代法翻转 - [4,2,7,1,3,6,9]
     */
    private static void testIterativeMethod(S93_Easy_226_翻转二叉树 solution) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        System.out.println("使用迭代法翻转树");
        System.out.println("原始树结构:");
        System.out.println("       4");
        System.out.println("      / \\");
        System.out.println("     2   7");
        System.out.println("    / \\ / \\");
        System.out.println("   1  3 6  9");

        TreeNode result = solution.invertTreeIterative(root);

        System.out.println("\n翻转后树结构:");
        System.out.println("       4");
        System.out.println("      / \\");
        System.out.println("     7   2");
        System.out.println("    / \\ / \\");
        System.out.println("   9  6 3  1");

        // 验证结果
        assert result.val == 4 : "根节点应该是4";
        assert result.left.val == 7 : "根节点的左子节点应该是7";
        assert result.right.val == 2 : "根节点的右子节点应该是2";
        assert result.left.left.val == 9 : "节点7的左子节点应该是9";
        assert result.left.right.val == 6 : "节点7的右子节点应该是6";
        assert result.right.left.val == 3 : "节点2的左子节点应该是3";
        assert result.right.right.val == 1 : "节点2的右子节点应该是1";

        System.out.println("✓ 迭代法翻转测试通过");
    }
}

